/*
1011. 在 D 天内送达包裹的能力
https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
难度:medium  彭珵  二分查找
*/


class Solution {
public:
    // 函数用于确定在给定天数内所需的最小船只容量
    int shipWithinDays(vector<int>& weights, int days) {
        // 初始化左边界为 weights 中的最大重量
        int l = INT_MIN;
        // 初始化右边界为所有重量的总和
        int r = 0;
        for (int weight : weights) {
            l = max(l, weight); // 找到最大重量
            r += weight; // 计算总重量
        }
        
        // 在 l 和 r 之间进行二分搜索
        while (l < r) {
            int mid = l + (r - l) / 2; // 计算中间容量
            int day = dayNeed(weights, mid); // 计算当前容量下所需的天数
            
            // 如果所需天数小于等于允许的天数，尝试更小的容量
            if (day <= days) 
                r = mid; // 将右边界移动到 mid
            else 
                l = mid + 1; // 将左边界移动到 mid + 1
        }
        
        return r; // 返回找到的最小容量
    }

    // 辅助函数，用于计算给定船只容量所需的天数
    int dayNeed(vector<int>& weights, int ability) {
        int res = 1; // 从一天开始计数
        int temp = 0; // 临时变量，用于跟踪当前负载
        
        for (int weight : weights) {
            // 如果添加此重量不超过能力，则将其添加到当前负载中
            if (temp + weight <= ability) {
                temp += weight;
                continue;
            }
            // 否则，需要新的一天来运送这个重量
            res++;
            temp = weight; // 将当前负载重置为当前重量
        }
        
        return res; // 返回所需的总天数
    }
};